/**
 * 931、下标路径最小和
 */
public class Exercise8 {
    public int minFallingPathSum(int[][] matrix) {
        // dp[i][j]: 到达i,j位置后，下标路径的最小值
        // 状态表达式：以dp[i][j]位置往上一层推
        int n = matrix.length;
        // 创建dp
        int[][] dp = new int[n + 1][n + 2];
        // 这里的dp多1行多2列是为了添加 辅助节点，进行初始化
        // 多出的第一行，初始化为0，为了得到matrix中第一行的最小值
        // 多出的两列，分为一左一右，初始化为最大值，防止在后面找 matrix的时候出现错误，防止把新增的列的值放进去
        for(int i = 1;i <= n;i++) {
            dp[i][0] = dp[i][n + 1] = Integer.MAX_VALUE;
        }
        for(int i = 1;i <= n;i++) {
            for(int j = 1;j <= n;j++) {
                dp[i][j] = Math.min(dp[i - 1][j - 1],Math.min(dp[i - 1][j],dp[i - 1][j + 1])) + matrix[i - 1][j - 1];
            }
        }
        int ret = Integer.MAX_VALUE;
        for(int j = 1;j <= n;j++) {
            ret = Math.min(ret,dp[n][j]);
        }
        return ret;
    }
}
